Abstract

Digital circles not only play an important role in various technological settings, but also provide a lively playground for more fundamental number-theoretical questions. In this paper, we present a new algorithm for the construction of digital circles on the integer lattice $\mathbb{Z}^2$, which makes sole use of the signum function. By briefly elaborating on the nature of discretization of circular paths, we then find that this algorithm recovers, in a space endowed with $\ell^1$-norm, the defining constant $\pi$ of a circle in $\mathbb{R}^2$.

Supplementary Information

Calculating $\overline{\pi}$ from the arithmetic mean $A(\pi_n)$

The path from the arithmetic mean $A(\pi_n)$ in Eq. (31) to the explicit expression of $\overline{\pi}$ in Eq. (32) is not as "straightforward" as suggested in the paper. Below, the deduction of $\overline{\pi}$ is presented in more detail.

We start by considering the arithmetic mean $A(\pi_n)$ of all $\pi_n(r)$, that is $$ A(\pi_n) = \frac{1}{2r} \sum\limits_{n=0}^{2r-1} \pi_n(r). $$ Utilizing (27), (28) and (30) in the paper, we obtain $$ \tag{S1} A(\pi_n) = 2 \sum\limits_{n=0}^{2r-1} \frac{1}{a_n(r)} = \frac{2}{r} \sum\limits_{n=0}^{2r-1} \frac{1}{\cos\left(\frac{n\pi}{4r}\right)+\sin\left(\frac{n\pi}{4r}\right)}. $$ To simplify the last equation, we first rewrite the denominator under the sum using $$ \sin(x) \pm \cos(y) = 2 \sin\left(\frac{1}{2}(x \pm y) \pm \frac{\pi}{4}\right) \cos\left(\frac{1}{2}(x \mp y) \mp \frac{\pi}{4}\right) $$ (see [1], relation 1.314.9$^*$). With this, (S1) takes the form \begin{eqnarray} A(\pi_n) & = & \frac{\sqrt{2}}{r} \sum\limits_{n=0}^{2r-1} \frac{1}{\sin\left(\frac{n\pi}{4r}+\frac{\pi}{4}\right)} \\ & = & \frac{2 \sqrt{2}}{r} \sum\limits_{n=0}^{2r-1} \sum\limits_{k=0}^{\infty} \frac{(-1)^{k+1} (2^{2k-1}-1) B_{2k}}{(2k)!} \left(\frac{\pi}{4}\right)^{2k-1} \left( \frac{n}{r}+1 \right)^{2k-1}, \end{eqnarray} where, in the last step, we used the power expansion of $1/\sin(x) \equiv \csc(x)$ in terms of Bernoulli numbers $B_n$ and the fact that $$ \frac{\pi}{4} \leq \left( \frac{n\pi}{4r}+\frac{\pi}{4} \right) < \frac{3 \pi}{4} $$ for all $r \geq 1, n \in [0,2r-1]$. Splitting off the inner sum the $k=0$ term and executing the sum over $n$ yields \begin{eqnarray} A(\pi_n) & = & \frac{4 \sqrt{2}}{\pi} \sum\limits_{n=0}^{2r-1} \frac{1}{n+r} + \frac{2 \sqrt{2}}{r} \sum\limits_{n=0}^{2r-1} \sum\limits_{k=1}^{\infty} \frac{(-1)^{k+1} (2^{2k-1}-1) B_{2k}}{(2k)!} \left(\frac{\pi}{4}\right)^{2k-1} \left( \frac{n}{r}+1 \right)^{2k-1} \\ & = & \frac{4 \sqrt{2}}{\pi} \big( \Psi(3r) - \Psi(r) \big) + 2 \sqrt{2} \sum\limits_{k=1}^{\infty} \frac{(-1)^{k+1} (2^{2k-1}-1) B_{2k}}{(2k)!} \left(\frac{\pi}{4}\right)^{2k-1} \frac{1}{r^{2k}} \big( \zeta(1-2k,r) - \zeta(1-2k,3r) \big), \end{eqnarray} where $\Psi(x)$ denotes the digamma function and $\zeta(n,x)$ the Hurwitz zeta function. Exploiting $$ \zeta(-n,x) = - \frac{B_{n+1}(x)}{n+1} $$ (see [2], Theorem 12.13), which holds for $n \geq 0$ and links the Hurwitz zeta to Bernoulli polynomials $$ B_{n}(x) = \sum\limits_{k=0}^n \binom{n}{k} B_{n-k} x^k, $$ we can further simplify $A(\pi_n)$ to $$ A(\pi_n) = \frac{4 \sqrt{2}}{\pi} \big( \Psi(3r) - \Psi(r) \big) + 2 \sqrt{2} \sum\limits_{k=1}^{\infty} \frac{(-1)^{k+1} (2^{2k-1}-1) B_{2k}}{(2k)! \, 2k} \left(\frac{\pi}{4}\right)^{2k-1} \frac{1}{r^{2k}} \big( B_{2k}(3r) - B_{2k}(r) \big). $$ Observing that $B_{n}(x)$ are polynomials of degree $n$ in $x$, and recalling that our assessment aims at the asymptotic limit $r \rightarrow \infty$, the last equation yields $$ A(\pi_n) = \frac{4 \sqrt{2}}{\pi} \big( \Psi(3r) - \Psi(r) \big) + 2 \sqrt{2} \sum\limits_{k=1}^{\infty} \frac{(-1)^{k+1} (2^{2k-1}-1) B_{2k}}{(2k)! \, 2k} \left(\frac{\pi}{4}\right)^{2k-1} ( 3^{2k}-1 ) + \mathcal{O}\left( \tfrac{1}{r} \right). $$ Performing now carefully the asymptotic limit $r \rightarrow \infty$, we finally obtain Eq. (32) in the paper: \begin{eqnarray} \overline{\pi} & := & \lim_{r \rightarrow \infty} A(\pi_n) \\ & = & \frac{2 \sqrt{2}}{\pi} \left( 2 \ln(3) + \ln(\tfrac{9}{8}) + \ln(8) - 2 \ln(16 (2-\sqrt{2}) + 2 \ln(\tfrac{16}{9} (\sqrt{2}+2)) \right) \\ & = & \frac{4 \sqrt{2}}{\pi} \left( \ln(2+\sqrt{2}) - \ln(2-\sqrt{2}) \right) \\ & \sim & 3.17406. \end{eqnarray}

Convergence behavior of $A(\pi_n)$ in Conjecture 1

A brief look at Figure 4 (bottom left) in the paper suggests that the convergence behavior in the case of the proper digital circle construction (based on the algorithm in Proposition 1) is rather acceptable. Some associated numbers are presented in Table S1 below.

Although much faster algorithms for the generation of $\pi$ are known, it has to be noted that the presentation of such a fast algorithm is not the goal of the paper. Instead, the study intends to show that it is, in principle, possible to generate a valid circle with its defining constant $\pi$ solely in a space with $\ell^1$-norm, without resorting to Euclidean notions.

The proof of Conjecture 1 and a more detailed study of the convergence behavior of the arithmetic mean $A(\pi_n)$ in Conjecture 1 is presented in [3].

Expressions for $\mathcal{A}_{\text{inner}}(r)$ and $\mathcal{A}_{\text{outer}}(r)$

Do algebraic expressions exist which deliver the total area of squares inside and outside the circle $S^1 \subset \mathbb{R}^2$, $\mathcal{A}_{\text{inner}}(r)$ and $\mathcal{A}_{\text{outer}}(r)$, respectively (see Figure 5 in the paper)?

Unfortunately, the short answer is no, and it is based on a simple argument.

For the sake of this argument, let us restrict to the area of the squares which reside fully inside the circle, $\mathcal{A}_{\text{inner}}(r)$. The argument for $\mathcal{A}_{\text{outer}}(r)$ follows similar lines. By construction, restricting to the integer lattice $\mathbb{Z}^2$, the total area of squares inside the circle is given by the number of grid points (nodes) on $\mathbb{Z}^2$ inside the circle, minus the number of points on the axes. Let us denote the former by $N(r)$ and the latter by $N_{axes}(r)$. We certainly have $N_{axes}(r) = 4r+1$ for a full circle of integer radius $r$, thus $$ \tag{S2} 4 \mathcal{A}_{\text{inner}}(r) = N(r) - 4r - 1 $$ (please recall that $\mathcal{A}_{\text{inner}}(r)$ refers to a quarter circle in the paper). Unfortunately, $N(r)$ in this equation is a bit more tricky to deal with. In fact, the sequence of $N(r)$ for $r \in \mathbb{N}$ (OEIS A000328) constitutes a well-known and still open problem in number theory, the Gauss's Circle Problem (e.g., see [4]). As so far no explicit algebraic or analytic expressions delivering the sequence $N(r)$ are known, due to (S2) there cannot exist yet an algebraic or analytic expression for $\mathcal{A}_{\text{inner}}(r)$. The same argument applies to $\mathcal{A}_{\text{outer}}(r)$.

However, and fortunately, the long answer is yes. In a forthcoming paper, both an explicit expression and recurrence equation for the sequence $N(r), r \in \mathbb{N}$ will be presented, which, together with (S2), then provide algebraic expressions for $\mathcal{A}_{\text{inner}}(r)$ and $\mathcal{A}_{\text{outer}}(r)$.